#ifndef CODICT_H
#define CODICT_H

/*
There are three kinds of slots in the table:

1. Unused.  de_key == de_value == NULL
   Does not hold an active (key, value) pair now and never did.  Unused can
   transition to Active upon key insertion.  This is the only case in which
   de_key is NULL, and is each slot's initial state.

2. Active.  de_key != NULL and de_key != dummy and de_value != NULL
   Holds an active (key, value) pair.  Active can transition to Dummy upon
   key deletion.  This is the only case in which de_value != NULL.

3. Dummy.  de_key == dummy and de_value == NULL
   Previously held an active (key, value) pair, but that was deleted and an
   active pair has not yet overwritten the slot.  Dummy can transition to
   Active upon key insertion.  Dummy slots cannot be made Unused again
   (cannot have de_key set to NULL), else the probe sequence in case of
   collision would have no way to know they were once active.
*/

/* DICT_MIN_SIZE is the minimum size of a dictionary.  This many slots are
 * allocated directly in the dict object (in the d_smalltable member).
 * It must be a power of 2, and at least 4.  8 allows dicts with no more
 * than 5 active entries to live in d_smalltable (and so avoid an
 * additional malloc); instrumentation suggested this suffices for the
 * majority of dicts (consisting mostly of usually-small instance dicts and
 * usually-small dicts created to pass keyword arguments).
 */
#define DICT_MIN_SIZE   8

typedef struct _CoDictEntry {
	/* Cached hash code of de_key.
	 */
    long de_hash;
    CoValue *de_key;
    CoValue *de_value;
} CoDictEntry;

/*
To ensure the lookup algorithm terminates, there must be at least one Unused
slot (NULL key) in the table.
The value d_fill is the number of non-NULL keys (sum of Active and Dummy);
d_used is the number of non-NULL, non-dummy keys (== the number of non-NULL
values == the number of Active items).
To avoid slowing down lookups on a near-full table, we resize the table when
it's two-thirds full.
*/
typedef struct {
    COVALUE_HEAD
    ssize_t d_fill;  /* # Active + # Dummy */
    ssize_t d_used;  /* # Active */

	/* The table contains d_mask + 1 slots, and that's a power of 2.
	 * We store the mask instead of the size because the mask is more
	 * frequently needed.
	 */
    ssize_t d_mask;

	/* d_table points to d_smalltable for small tables, else to
	 * additional malloc'ed memory.  d_table is never NULL!  This rule
	 * saves repeated runtime null-tests in the workhorse getitem and
	 * setitem calls.
	 */
    CoDictEntry *d_table;
    CoDictEntry d_smalltable[DICT_MIN_SIZE];
} CoDict;

extern CoType CoDict_Type;

#define CODICT_CHECK(self)   CO_CHECK_TYPE(self, &CoDict_Type)

CoValue *CoDict_New(void);
CoValue *CoDict_GetItem(CoValue *self, CoValue *key);
int CoDict_SetItem(CoValue *self, CoValue *key, CoValue *value);
int CoDict_DelItem(CoValue *self, CoValue *key);
void CoDict_Clear(CoValue *self);

#endif
